//
// Description: 85. 最大矩形
// Created by Loading on 2022/6/17.
//

#include <bits/stdc++.h>

using namespace std;

int maximalRectangle(vector<vector<char>> &matrix) {
    int m = matrix.size();
    int n = matrix[0].size();

    // left[i][j] 表示以位置 (i,j) 结尾的连续 1 的个数
    int left[m][n];
    // 初始化
    memset(left, 0, sizeof left);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == '1') {
                left[i][j] = (j > 0 ? left[i][j - 1] : 0) + 1;
            }
        }
    }

    int area = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (left[i][j] != 0) {
                int width = left[i][j];
                // 遍历高度
                for (int k = i; k >= 0; --k) {
                    if (left[k][j] != 0) {
                        // 宽度选择最小，更新最大面积
                        width = min(width, left[k][j]);
                        area = max(area, width * (i - k + 1));
                    } else {
                        break;
                    }
                }
            }
        }
    }

    return area;
}

int main() {
    vector<vector<char>> matrix{{'1', '0', '1', '0', '0'},
                                {'1', '0', '1', '1', '1'},
                                {'1', '1', '1', '1', '1'},
                                {'1', '0', '0', '1', '0'}};

    auto res = maximalRectangle(matrix);

    cout << res << endl;

    return 0;
}